#ifndef STX_ALGORITHM_SEARCH_N_HPP
#define STX_ALGORITHM_SEARCH_N_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class BinaryPredicate, class ForwardIterator, class Size, class T>
inline ForwardIterator
search_n_impl(
    ForwardIterator first,
    ForwardIterator last,
    Size count,
    const T& value,
    BinaryPredicate pred,
    std::forward_iterator_tag)
{
    if (count <= 0) {
        return first;
    }
    while (1) {
        // Find first element in sequence that matchs value, with a mininum of loop checks
        while (1) {
            if (first == last) { // return last if no element matches value
                return last;
            }
            if (pred(*first, value)) {
                break;
            }
            ++first;
        }
        // *first matches value, now match elements after here
        ForwardIterator m = first;
        Size c(0);
        while (1) {
            if (++c == count) { // If pattern exhausted, first is the answer (works for 1 element pattern)
                return first;
            }
            if (++m == last) { // Otherwise if source exhaused, pattern not found
                return last;
            }
            if (!pred(*m, value)) { // if there is a mismatch, restart with a new first
                first = m;
                ++first;
                break;
            } // else there is a match, check next elements
        }
    }
}

template <class BinaryPredicate, class RandomAccessIterator, class Size, class T>
inline RandomAccessIterator
search_n_impl(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Size count,
    const T& value,
    BinaryPredicate pred,
    std::random_access_iterator_tag)
{
    if (count <= 0) {
        return first;
    }
    Size len = static_cast<Size>(last - first);
    if (len < count) {
        return last;
    }
    const RandomAccessIterator s = last - (count - 1); // Start of pattern match can't go beyond here
    while (1) {
        // Find first element in sequence that matchs value, with a mininum of loop checks
        while (1) {
            if (first == s) { // return last if no element matches value
                return last;
            }
            if (pred(*first, value)) {
                break;
            }
            ++first;
        }
        // *first matches value, now match elements after here
        RandomAccessIterator m = first;
        Size c(0);
        while (1) {
            if (++c == count) { // If pattern exhausted, first is the answer (works for 1 element pattern)
                return first;
            }
            ++m; // no need to check range on m because s guarantees we have enough source
            if (!pred(*m, value)) { // if there is a mismatch, restart with a new first
                first = m;
                ++first;
                break;
            }   // else there is a match, check next elements
        }
    }
}

template <class ForwardIterator, class Size, class T, class BinaryPredicate>
inline ForwardIterator
search_n(
    ForwardIterator first,
    ForwardIterator last,
    Size count,
    const T& value,
    BinaryPredicate pred)
{
    return stx::search_n_impl<typename add_lvalue_reference<BinaryPredicate>::type>(
        first,
        last,
        count,
        value,
        pred,
        typename std::iterator_traits<ForwardIterator>::iterator_category());
}

template <class ForwardIterator, class Size, class T>
inline ForwardIterator
search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value)
{
    typedef typename std::iterator_traits<ForwardIterator>::value_type v;
    return stx::search_n(first, last, count, value, equal_to<v, T>());
}

} // namespace stx

#endif // STX_ALGORITHM_SEARCH_N_HPP
